package array

// https://leetcode-cn.com/problems/max-consecutive-ones-iii/
// 最大连续都为1 的个数
// 算法: 滑动窗口（双指针）
// 实现依据: 既然答案是要得到最长连续1 的个数，那么翻转0 也一定是要连续的，所以可以连续遍历
// 时间复杂度O(len(A))
func LongestOnes(A []int, K int) int {
	if len(A) == 0 {
		return 0
	}
	start, end := 0, 0
	remainFlip := K
	maxLen := 0
	currentLen := 0
	for end < len(A) && start <= end {
		if A[end] == 0 {
			if remainFlip > 0 {
				remainFlip--
				currentLen = end - start + 1
				end++
			} else {
				// 连续0 已经用完了，就需要移动起始位置，直到有空余的翻转次数
				// 特殊情况: 起始位置和结束位置一样，可说明K = 0，那么结束位置也要跟着移动
				if start != end && A[start] == 0 {
					remainFlip++
				} else if start == end {
					end++
				}
				start++
			}
		} else {
			// 当前位置就是1，不需要翻转，直接移动结束位置即可
			currentLen = end - start + 1
			end++
		}
		if currentLen > maxLen {
			maxLen = currentLen
		}
	}
	return maxLen
}
